#include <iostream>
#include <string>
#include <vector>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};


class BSTIterator
{
public:
    BSTIterator(TreeNode *root)
    {
        TreeNode* ptr=root;
        while(ptr)
            {
                list.push_back(ptr);
                ptr=ptr->left;
            }
    }

    /** @return whether we have a next smallest number */
    bool hasNext()
    {
        bool r=list.size()!=0;
        return r;
    }

    /** @return the next smallest number */
    int next()
    {
        TreeNode* ptr=list[list.size()-1];
        int val=ptr->val;

        //1
        if(ptr->right!=NULL)
            {
                ptr=ptr->right;
                while(ptr)
                    {
                        list.push_back(ptr);
                        ptr=ptr->left;
                    }
            }
        else
            {
                if(list.size()==1)
                    list.pop_back();
                else
                    {
                        //2
                        if(ptr==list[list.size()-2]->left)
                            list.pop_back();
                        //3
                        else
                            {
                                list.pop_back();
                                while(list.size()!=0&&list[list.size()-1]->val<val)
                                    {
                                        list.pop_back();
                                    }
                            }
                    }
            }
        return val;
    }
private:
    vector<TreeNode*> list;
};

int main()
{
    TreeNode t1(9);
    TreeNode t2(7);
    TreeNode t3(13);
    TreeNode t4(6);
    TreeNode t5(8);
    TreeNode t6(11);
    TreeNode t7(14);
    TreeNode t8(12);
    t1.left=&t2;
    t1.right=&t3;
    t2.left=&t4;
    t2.right=&t5;
    t3.left=&t6;
    t3.right=&t7;
    t6.right=&t8;

    TreeNode t9(2);
    TreeNode t10(1);
    t9.left=&t10;
    BSTIterator it(&t9);
    while(it.hasNext())
        {
            cout<<it.next()<<",";
        }
}